{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Delete Node in a Linked List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #linked-list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: deleteNode"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #删除链表中的节点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一个单链表的&nbsp;<code>head</code>，我们想删除它其中的一个节点&nbsp;<code>node</code>。</p>\n",
    "\n",
    "<p>给你一个需要删除的节点&nbsp;<code>node</code>&nbsp;。你将&nbsp;<strong>无法访问</strong>&nbsp;第一个节点&nbsp;&nbsp;<code>head</code>。</p>\n",
    "\n",
    "<p>链表的所有值都是 <b>唯一的</b>，并且保证给定的节点&nbsp;<code>node</code>&nbsp;不是链表中的最后一个节点。</p>\n",
    "\n",
    "<p>删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>给定节点的值不应该存在于链表中。</li>\n",
    "\t<li>链表中的节点数应该减少 1。</li>\n",
    "\t<li><code>node</code>&nbsp;前面的所有值顺序相同。</li>\n",
    "\t<li><code>node</code>&nbsp;后面的所有值顺序相同。</li>\n",
    "</ul>\n",
    "\n",
    "<p><strong>自定义测试：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>对于输入，你应该提供整个链表&nbsp;<code>head</code>&nbsp;和要给出的节点&nbsp;<code>node</code>。<code>node</code>&nbsp;不应该是链表的最后一个节点，而应该是链表中的一个实际节点。</li>\n",
    "\t<li>我们将构建链表，并将节点传递给你的函数。</li>\n",
    "\t<li>输出将是调用你函数后的整个链表。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/01/node1.jpg\" style=\"height: 286px; width: 400px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [4,5,1,9], node = 5\n",
    "<strong>输出：</strong>[4,1,9]\n",
    "<strong>解释：</strong>指定链表中值为&nbsp;5&nbsp;的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -&gt; 1 -&gt; 9\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/01/node2.jpg\" style=\"height: 315px; width: 400px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [4,5,1,9], node = 1\n",
    "<strong>输出：</strong>[4,5,9]\n",
    "<strong>解释：</strong>指定链表中值为&nbsp;1&nbsp;的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -&gt; 5 -&gt; 9</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>链表中节点的数目范围是 <code>[2, 1000]</code></li>\n",
    "\t<li><code>-1000 &lt;= Node.val &lt;= 1000</code></li>\n",
    "\t<li>链表中每个节点的值都是 <strong>唯一</strong> 的</li>\n",
    "\t<li>需要删除的节点 <code>node</code> 是 <strong>链表中的节点</strong> ，且 <strong>不是末尾节点</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [delete-node-in-a-linked-list](https://leetcode.cn/problems/delete-node-in-a-linked-list/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [delete-node-in-a-linked-list](https://leetcode.cn/problems/delete-node-in-a-linked-list/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,5,1,9]\\n5', '[4,5,1,9]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next= node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val=node.next.val\n",
    "        node.next=node.next.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        node.val = node.next.val\n",
    "        node.next=node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, c):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        c.val = c.next.val\n",
    "        c.next = c.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node1=node2=node\n",
    "        while(node1.next):\n",
    "            node1.val=node1.next.val\n",
    "            node2=node1\n",
    "            node1=node1.next\n",
    "        node2.next=None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        p = node\n",
    "        while p.next.next:\n",
    "            p.val = p.next.val\n",
    "            p = p.next\n",
    "        p.val = p.next.val\n",
    "        p.next = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val=node.next.val\n",
    "        node.next=node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val=node.next.val\n",
    "        node.next=node.next.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val=node.next.val;node.next=node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, c):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        c.val = c.next.val\n",
    "        c.next = c.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val; node.next = node.next.next;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        p=node\n",
    "        q=node.next\n",
    "        while q!=None:\n",
    "            p.val=q.val\n",
    "            t=p\n",
    "            p=p.next\n",
    "            q=q.next\n",
    "        t.next=None\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "      \n",
    "        node.val=node.next.val\n",
    "        node.next=node.next.next\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val=node.next.val\n",
    "        node.next=node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        next_node = node.next\n",
    "        after_next_node = next_node.next\n",
    "        node.val = next_node.val\n",
    "        node.next = after_next_node\n",
    "        return "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val=node.next.val\n",
    "        node.next=node.next.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val=node.next.val\n",
    "        node.next=node.next.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        #node模拟下一个节点值\n",
    "        #在将node.next改为模拟节点的下一个节点\n",
    "        #即将node的下一个节点消去\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val    #### 后面的数值拷贝过来\n",
    "        node.next = node.next.next  #### 单元也移除"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val=node.next.val\n",
    "        node.next=node.next.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        cur = node\n",
    "        while cur.next and cur.next.next:\n",
    "            cur.val = cur.next.val\n",
    "            cur = cur.next\n",
    "        cur.val = cur.next.val\n",
    "        cur.next = None        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        cur_node = head\n",
    "        while cur_node:\n",
    "            for i in range(m-1):\n",
    "                if cur_node:\n",
    "                    cur_node = cur_node.next\n",
    "                else:\n",
    "                    return head\n",
    "            if cur_node:\n",
    "                step_node = cur_node.next\n",
    "            else:\n",
    "                return head\n",
    "            for j in range(n):\n",
    "                if step_node:\n",
    "                    step_node = step_node.next\n",
    "                else:\n",
    "                    cur_node.next = step_node\n",
    "                    return head\n",
    "            cur_node.next = step_node\n",
    "            cur_node = step_node\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        return self.answer_1(head, m, n)\n",
    "\n",
    "    def answer_1(self, head, m, n):\n",
    "        curr = head\n",
    "        last = head\n",
    "\n",
    "        while curr:\n",
    "            p , q = m, n\n",
    "            while p  and curr:\n",
    "                last = curr\n",
    "                curr = curr.next\n",
    "                p -= 1\n",
    "\n",
    "            while q and curr:\n",
    "                curr = curr.next\n",
    "                q -= 1\n",
    "            last.next = curr\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        cur = head\n",
    "        tail = head\n",
    "\n",
    "        while cur:\n",
    "            mc = m\n",
    "            nc = n\n",
    "            while cur and mc > 0:\n",
    "                tail = cur\n",
    "                cur = cur.next\n",
    "                mc -= 1\n",
    "            while cur and nc > 0:\n",
    "                nc -= 1\n",
    "                cur = cur.next\n",
    "            tail.next = cur\n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        cur_node = head\n",
    "        ctr = 1\n",
    "        \n",
    "        while True:\n",
    "            while cur_node and ctr < m:\n",
    "                cur_node = cur_node.next\n",
    "                ctr += 1\n",
    "            \n",
    "            if not cur_node:\n",
    "                return head\n",
    "            \n",
    "            del_ctr = 0\n",
    "            del_node = cur_node\n",
    "            while del_node and del_ctr < n:\n",
    "                del_node = del_node.next\n",
    "                del_ctr += 1\n",
    "            \n",
    "            if not del_node:\n",
    "                cur_node.next = None\n",
    "            else:\n",
    "                cur_node.next = del_node.next\n",
    "                ctr = 1\n",
    "            cur_node = cur_node.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        \n",
    "        p=head\n",
    "\n",
    "        while p:\n",
    "\n",
    "            t=1\n",
    "            while p and t<m:\n",
    "                t+=1\n",
    "                p=p.next\n",
    "            q=p\n",
    "            if p:\n",
    "                t=0\n",
    "                while q and t<=n:\n",
    "                    q=q.next\n",
    "                    t+=1\n",
    "                p.next=q\n",
    "                p=p.next\n",
    "        return head\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        dummy = ListNode(0)\n",
    "        dummy.next = head \n",
    "        cur = dummy\n",
    "        while cur.next:\n",
    "            p, q = m, n \n",
    "            while p > 0 and cur.next:\n",
    "                p -= 1\n",
    "                cur = cur.next \n",
    "            while q > 0 and cur.next:\n",
    "                q -= 1\n",
    "                cur.next = cur.next.next\n",
    "        \n",
    "        return dummy.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        if not head:\n",
    "            return\n",
    "        left, right = head, head\n",
    "        idx = -1\n",
    "        while right != None:\n",
    "            idx += 1\n",
    "            cur = idx % (m+n)\n",
    "            # print(left.val, right.val, cur)\n",
    "            if cur < m-1:\n",
    "                left = left.next\n",
    "                right = right.next\n",
    "            elif n+m-1>=cur >= m-1:\n",
    "                left.next = right.next\n",
    "                right = right.next\n",
    "                if cur == n+m-1:\n",
    "                    left = right\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        dummy = ListNode()\n",
    "        dummy.next = head\n",
    "        cur = dummy\n",
    "        while cur.next:\n",
    "            q,p = m,n\n",
    "            while cur.next and q>0:\n",
    "                cur = cur.next\n",
    "                q -=1\n",
    "            while cur.next and p>0:\n",
    "                p-=1\n",
    "                cur.next = cur.next.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        point=head\n",
    "        while point:\n",
    "            try:\n",
    "                for i in range(1,m):\n",
    "                    point=point.next\n",
    "                for j in range(n):\n",
    "                    point.next=point.next.next\n",
    "                point=point.next\n",
    "            except:\n",
    "                return head\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        low = head\n",
    "        high = head\n",
    "        \n",
    "        while True:\n",
    "            for _ in range(m-1):\n",
    "                if low.next:\n",
    "                    low = low.next\n",
    "                else:\n",
    "                    return head\n",
    "\n",
    "            for _ in range(m+n):\n",
    "                if high.next:\n",
    "                    high = high.next\n",
    "                else:\n",
    "                    low.next = None\n",
    "                    return head\n",
    "        \n",
    "            low.next = high\n",
    "            low = high"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        cur = head\n",
    "        while cur != None:\n",
    "            i = 0\n",
    "            while cur != None and i < m-1:\n",
    "                cur = cur.next\n",
    "                i += 1\n",
    "            pos = cur\n",
    "            if pos == None:\n",
    "                return head\n",
    "            i = 0\n",
    "            cur = cur.next\n",
    "            while cur != None and i < n:\n",
    "                pos.next = cur.next\n",
    "                cur = cur.next\n",
    "                i += 1\n",
    "        return head\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        p = head\n",
    "        q = head\n",
    "        while p:\n",
    "            m1 = n1 = 0\n",
    "            while m1<m-1 and p:\n",
    "                p = p.next\n",
    "                m1+=1\n",
    "            if not p:\n",
    "                break\n",
    "            q = p\n",
    "            while n1 < n and q:\n",
    "                q = q.next\n",
    "                n1 += 1\n",
    "            if  q:\n",
    "                p.next = q.next\n",
    "            else:\n",
    "                p.next = None\n",
    "            p = p.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        tmp = ListNode(next = head)\n",
    "        while tmp.next != None:\n",
    "            for i in range(m):\n",
    "                tmp = tmp.next\n",
    "                if tmp == None:\n",
    "                    break\n",
    "            if tmp == None or tmp.next == None:\n",
    "                break\n",
    "\n",
    "            for i in range(n):\n",
    "                if tmp.next == None:\n",
    "                    break\n",
    "                tmp.next = tmp.next.next\n",
    "\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        cur = head\n",
    "        while cur:\n",
    "            for i in range(m-1):\n",
    "                if cur:\n",
    "                    cur = cur.next\n",
    "                else:\n",
    "                    return head\n",
    "\n",
    "            if cur:\n",
    "                kk = cur.next\n",
    "            else:\n",
    "                return head\n",
    "            \n",
    "            for j in range(n):\n",
    "                if kk:\n",
    "                    kk = kk.next\n",
    "                else:\n",
    "                    cur.next = kk\n",
    "                    return head\n",
    "            \n",
    "            cur.next = kk\n",
    "            cur = kk\n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        curNode = head\n",
    "\n",
    "        while next != None:\n",
    "            for i in range(m-1):\n",
    "                if curNode:\n",
    "                    curNode = curNode.next\n",
    "                \n",
    "            if not curNode:\n",
    "                break\n",
    "\n",
    "            for j in range(n):\n",
    "                if curNode.next:\n",
    "                    curNode.next = curNode.next.next\n",
    "                else:\n",
    "                    break\n",
    "            \n",
    "            curNode = curNode.next\n",
    "            \n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        node = head\n",
    "        while True:\n",
    "            i = 0\n",
    "            while node is not None and i < m - 1:\n",
    "                # 经过m个节点\n",
    "                node = node.next\n",
    "                i += 1\n",
    "            if node is None:\n",
    "                break\n",
    "            pre = node\n",
    "            while node is not None and i < m + n:\n",
    "                node = node.next\n",
    "                i += 1\n",
    "            if pre is not None:\n",
    "                pre.next = node\n",
    "            if pre is None or node is None:\n",
    "                break\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        if not head:\n",
    "            return None\n",
    "        a=b=head\n",
    "        c,d=m,n\n",
    "        while m-1 and a.next:\n",
    "            a,b=a.next,b.next\n",
    "            m-=1\n",
    "        while n and b.next:\n",
    "            b=b.next\n",
    "            n-=1\n",
    "        a.next=self.deleteNodes(b.next, c, d)\n",
    "        return head\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        cur = head\n",
    "        while cur:\n",
    "            for _ in range(m - 1):\n",
    "                if cur:\n",
    "                    cur = cur.next\n",
    "                else:\n",
    "                    return head\n",
    "            if cur:\n",
    "                tmp = cur.next\n",
    "            else:\n",
    "                return head\n",
    "            \n",
    "            for _ in range(n):\n",
    "                if tmp:\n",
    "                    tmp = tmp.next\n",
    "                else:\n",
    "                    cur.next = tmp\n",
    "                    return head\n",
    "            cur.next = tmp\n",
    "            cur = tmp\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        # m + n，每 m + n个节点中，保留前m个，删去后n个\n",
    "        cur = head\n",
    "        tmp = 1\n",
    "        while cur and cur.next:\n",
    "            if tmp < m:\n",
    "                cur = cur.next\n",
    "            else:\n",
    "                cur.next = cur.next.next\n",
    "            tmp = (tmp + 1) % (m + n)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        cur = head\n",
    "        end = False\n",
    "        while not end:\n",
    "            for i in range(m-1):\n",
    "                if cur:\n",
    "                    cur = cur.next\n",
    "                else:\n",
    "                    end = True\n",
    "                    break\n",
    "            if end:\n",
    "                break\n",
    "            if not cur:\n",
    "                break\n",
    "            last = cur\n",
    "            for i in range(n+1):\n",
    "                if cur:\n",
    "                    cur = cur.next\n",
    "                else:\n",
    "                    end = True\n",
    "                    break\n",
    "            last.next = cur\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        prehead = ListNode(0,head)\n",
    "        i = 1\n",
    "        while head and i<m:\n",
    "            head = head.next\n",
    "            i+=1\n",
    "        if not head:\n",
    "            return prehead.next\n",
    "        tmp = head.next\n",
    "        i = 0\n",
    "        while tmp and i<n:\n",
    "            tmp = tmp.next\n",
    "            i+=1\n",
    "        head.next = tmp\n",
    "        if tmp:\n",
    "            head.next = self.deleteNodes(tmp,m,n)\n",
    "        return prehead.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        dummy = ListNode(-1)#创建一个dummy指针\n",
    "        dummy.next = head#dummy的next指向head\n",
    "        cur = dummy#现任节点\n",
    "\n",
    "        while (cur):#cur == None时退出while循环\n",
    "            for i in range(0, m):#从dummy开始，往前找m个位置，个数不足m个, 终止循环返回结果\n",
    "                if (cur == None) : \n",
    "                    break\n",
    "                cur = cur.next#现任节点进行右移\n",
    "\n",
    "            if (cur == None) :\n",
    "                break\n",
    "            for i in range(0, n):\n",
    "                if (cur.next == None) :\n",
    "                    break; #往前找n个位置，个数不足n个, 终止循环返回结果\n",
    "                cur.next = cur.next.next#现任节点next指向cur.next.next节点，则删除了后一节点\n",
    "\n",
    "        return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        if not head:\n",
    "            return None\n",
    "        \n",
    "        curr = head\n",
    "        while curr:\n",
    "            count = 1\n",
    "            while curr and count < m:\n",
    "                curr = curr.next\n",
    "                count += 1\n",
    "            \n",
    "            if not curr:\n",
    "                break\n",
    "            \n",
    "            res = n\n",
    "            while curr.next and res > 0:\n",
    "                curr.next = curr.next.next\n",
    "                res -= 1\n",
    "            \n",
    "            curr = curr.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        dummy = ListNode(0)\n",
    "        dummy.next = head \n",
    "        cur = dummy\n",
    "        while cur.next:\n",
    "            p, q = m, n \n",
    "            while p > 0 and cur.next:\n",
    "                p -= 1\n",
    "                cur = cur.next \n",
    "            while q > 0 and cur.next:\n",
    "                q -= 1\n",
    "                cur.next = cur.next.next\n",
    "        \n",
    "        return dummy.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        dummy = ListNode(-1)\n",
    "        dummy.next = head \n",
    "        cur = dummy \n",
    "        while(cur):\n",
    "            for i in range(m):\n",
    "                if(cur == None):\n",
    "                    break  \n",
    "                cur = cur.next \n",
    "            if(cur == None):\n",
    "                break \n",
    "            for i in range(n):\n",
    "                if(cur.next == None):\n",
    "                    break \n",
    "                cur.next = cur.next.next \n",
    "        return head\n",
    "        # dummy = ListNode(-1)\n",
    "        # dummy.next = head\n",
    "        # cur = dummy\n",
    "        # while (cur):\n",
    "        #     for i in range(0, m):\n",
    "        #         if (cur == None) : # less than m elements left, break\n",
    "        #             break\n",
    "        #         cur = cur.next\n",
    "\n",
    "        #     if (cur == None) :\n",
    "        #         break\n",
    "        #     for i in range(0, n):\n",
    "        #         if (cur.next == None) :\n",
    "        #             break; # nothing left to be deleted\n",
    "        #         # next =cur.next\n",
    "        #         cur.next = cur.next.next\n",
    "\n",
    "        # return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        dummy = ListNode(0)\n",
    "        dummy.next = head \n",
    "        cur = dummy\n",
    "        while cur.next:\n",
    "            p, q = m, n \n",
    "            while p > 0 and cur.next:\n",
    "                p -= 1\n",
    "                cur = cur.next \n",
    "            while q > 0 and cur.next:\n",
    "                q -= 1\n",
    "                cur.next = cur.next.next\n",
    "        \n",
    "        return dummy.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        dummy = ListNode(-1)\n",
    "        dummy.next = head\n",
    "        cur = dummy\n",
    "        while (cur):\n",
    "            for i in range(0, m):\n",
    "                if (cur == None) : # less than m elements left, break\n",
    "                    break\n",
    "                cur = cur.next\n",
    "\n",
    "            if (cur == None) :\n",
    "                break\n",
    "            for i in range(0, n):\n",
    "                if (cur.next == None) :\n",
    "                    break; # nothing left to be deleted\n",
    "                next =cur.next\n",
    "                cur.next = cur.next.next\n",
    "\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        cur = head\n",
    "\n",
    "        while True:\n",
    "            i, j = m - 1, n + 1\n",
    "            while cur and i:\n",
    "                cur = cur.next\n",
    "                i -= 1\n",
    "            nxt = cur\n",
    "            while nxt and j:\n",
    "                nxt = nxt.next\n",
    "                j -= 1\n",
    "            if not cur:\n",
    "                return head\n",
    "            cur.next = nxt\n",
    "            cur = nxt\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        p = head\n",
    "        cnt = 1\n",
    "        while p:\n",
    "            if cnt == m:\n",
    "                q = p\n",
    "                while cnt < m+n and q.next:\n",
    "                    q = q.next\n",
    "                    cnt += 1\n",
    "                p.next = q.next\n",
    "                p = q.next\n",
    "                cnt = 1\n",
    "            else:\n",
    "                p = p.next\n",
    "                cnt += 1\n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        index = head\n",
    "        \n",
    "        while index != None:\n",
    "            cm = m\n",
    "            cn = n\n",
    "            while cm > 0:\n",
    "                if index != None:\n",
    "                    cm -= 1\n",
    "                    temp = index\n",
    "                    index = index.next\n",
    "                else: break\n",
    "                    \n",
    "            while cn > 0:\n",
    "                if index != None:\n",
    "                    cn -= 1\n",
    "                    index = index.next\n",
    "                    temp.next = index\n",
    "                else: break\n",
    "        \n",
    "        return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        cur=head\n",
    "        while cur:\n",
    "            for i in range(m-1):\n",
    "                if cur:\n",
    "                    cur=cur.next\n",
    "                else:\n",
    "                    return head\n",
    "            if cur:\n",
    "                kk=cur.next\n",
    "            else:\n",
    "                return head\n",
    "            for j in range(n):\n",
    "                if kk:\n",
    "                    kk=kk.next\n",
    "                else:\n",
    "                    cur.next=kk\n",
    "                    return head\n",
    "            cur.next=kk\n",
    "            cur=kk\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        dummy = ListNode(-1)\n",
    "        dummy.next = head\n",
    "        cur = dummy\n",
    "        while cur.next:\n",
    "            p, q = m, n\n",
    "            while p>0 and cur.next:\n",
    "                p -= 1\n",
    "                cur = cur.next\n",
    "            while q>0 and cur.next:\n",
    "                q -= 1\n",
    "                cur.next = cur.next.next\n",
    "        return dummy.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        count = 1\n",
    "        pre = cur = head\n",
    "        while cur:\n",
    "            while cur and (0 < count % (m + n) <= m):\n",
    "                pre = cur\n",
    "                cur = cur.next\n",
    "                count += 1\n",
    "            while cur and (count % (m + n) > m or count % (m + n) == 0):\n",
    "                cur = cur.next\n",
    "                count += 1\n",
    "            pre.next = cur\n",
    "\n",
    "        return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        dummy = ListNode(0)\n",
    "        dummy.next = head\n",
    "        cur = dummy\n",
    "        while cur.next:\n",
    "            p,q = m,n\n",
    "            while p > 0 and cur.next:\n",
    "                p -= 1\n",
    "                cur = cur.next\n",
    "            while q > 0 and cur.next:     \n",
    "                q -= 1\n",
    "                cur.next = cur.next.next   # 直接改变cur的后继结点。\n",
    "\n",
    "        return dummy.next\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        pred_head = ListNode(-1, head)\n",
    "        node_pre = pred_head\n",
    "        nxt_node = pred_head\n",
    "        while node_pre:\n",
    "            idx_m, idx_n = m, n\n",
    "            for i in range(m):\n",
    "                if not node_pre:\n",
    "                    break\n",
    "                if not node_pre:\n",
    "                    break\n",
    "                node_pre = node_pre.next\n",
    "            for j in range(n):\n",
    "                if not node_pre or not node_pre.next:\n",
    "                    break\n",
    "                node_pre.next = node_pre.next.next\n",
    "\n",
    "        return pred_head.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        dummy = ListNode(0)\n",
    "        dummy.next = head\n",
    "        cur = dummy\n",
    "        while cur.next:\n",
    "            p, q = m, n\n",
    "            while p > 0 and cur.next:\n",
    "                p -= 1\n",
    "                cur = cur.next\n",
    "            while q > 0 and cur.next:\n",
    "                q -= 1\n",
    "                cur.next = cur.next.next\n",
    "        \n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        cur = head\n",
    "\n",
    "        while cur:\n",
    "            for _ in range(m - 1):\n",
    "                if cur:\n",
    "                    cur = cur.next\n",
    "            if not cur:\n",
    "                break\n",
    "            prev = cur\n",
    "            for _ in range(n + 1):\n",
    "                if cur:\n",
    "                    cur = cur.next\n",
    "            prev.next = cur\n",
    "        return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        cnt = -1\n",
    "        cur = dummy = ListNode(-1, head)\n",
    "        while cur:\n",
    "            cur = cur.next\n",
    "            cnt = (cnt + 1) % (m + n)\n",
    "            if cnt < m:\n",
    "                dummy.next = cur\n",
    "                dummy = cur\n",
    "            else:\n",
    "                continue\n",
    "        if dummy: dummy.next = None\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        pre = head\n",
    "        while True:\n",
    "            for _ in range(m-1):\n",
    "                if pre:\n",
    "                    pre = pre.next\n",
    "            \n",
    "            cur = pre\n",
    "            for _ in range(n+1):\n",
    "                if cur:\n",
    "                    cur = cur.next\n",
    "            if pre:\n",
    "                pre.next = cur\n",
    "                pre = cur\n",
    "            else:\n",
    "                break\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        left, right = head, head\n",
    "        remain = 1\n",
    "        remove = 0\n",
    "        while left and right:\n",
    "            if remain < m:\n",
    "                left = left.next\n",
    "                right = right.next\n",
    "                remain += 1\n",
    "            else:\n",
    "                remain = 0\n",
    "                while remove <= n and right:\n",
    "                    right = right.next\n",
    "                    remove += 1\n",
    "                left.next = right\n",
    "                remove = 1\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        cur = head\n",
    "        pre = None\n",
    "        while cur:\n",
    "            count_m = 0\n",
    "            while count_m < m and cur:\n",
    "                pre = cur\n",
    "                cur = cur.next\n",
    "                count_m += 1\n",
    "            count_n = 0\n",
    "            while count_n < n and cur:\n",
    "                cur = cur.next\n",
    "                pre.next = cur\n",
    "                count_n += 1\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        dummy = ListNode(-1)\n",
    "        dummy.next = head\n",
    "        cur = dummy\n",
    "        while (cur):\n",
    "            for i in range(0, m):\n",
    "                if (cur == None) : # less than m elements left, break\n",
    "                    break\n",
    "                cur = cur.next\n",
    "\n",
    "            if (cur == None) :\n",
    "                break\n",
    "            for i in range(0, n):\n",
    "                if (cur.next == None) :\n",
    "                    break; # nothing left to be deleted\n",
    "                # next =cur.next\n",
    "                cur.next = cur.next.next\n",
    "\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        dummy = ListNode(0)\n",
    "        dummy.next = head\n",
    "        cur = dummy\n",
    "        while cur.next:\n",
    "            p,q = m,n\n",
    "            while p and cur.next:\n",
    "                cur = cur.next\n",
    "                p-=1\n",
    "            while q and cur.next:\n",
    "                cur.next = cur.next.next\n",
    "                q-=1\n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        dummpy = ListNode(0)\n",
    "        dummpy.next = head\n",
    "        cur = dummpy\n",
    "\n",
    "        while cur.next:\n",
    "            for i in range(m):\n",
    "                if cur.next:\n",
    "                    cur = cur.next\n",
    "            for i in range(n):\n",
    "                if cur.next:\n",
    "                    cur.next = cur.next.next\n",
    "\n",
    "        return dummpy.next\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        low = high = head\n",
    "        while True:\n",
    "            for _ in range(m -1):\n",
    "                if low.next: low = low.next\n",
    "                else: return head\n",
    "            for _ in range(m + n):\n",
    "                if high.next: high = high.next \n",
    "                else: \n",
    "                    low.next = None\n",
    "                    return head\n",
    "            low.next = high \n",
    "            low = high\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        cur = head  \n",
    "        while cur:\n",
    "            for i in range(m-1):\n",
    "                if cur:\n",
    "                    cur = cur.next \n",
    "                else:\n",
    "                    return head   \n",
    "            if cur:\n",
    "                kk = cur.next \n",
    "            else:\n",
    "                return head \n",
    "            for j in range(n):\n",
    "                if kk:\n",
    "                    kk = kk.next \n",
    "                else:\n",
    "                    cur.next = kk \n",
    "                    return head   \n",
    "            cur.next = kk\n",
    "            cur = kk \n",
    "        return head \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        if not head: return None\n",
    "        a = b = head\n",
    "        c, d = m, n\n",
    "        while m-1 and a.next:\n",
    "            a, b = a.next, b.next\n",
    "            m -=1\n",
    "        while n and b.next:\n",
    "            b = b.next\n",
    "            n-=1\n",
    "        a.next = self.deleteNodes(b.next, c, d)\n",
    "\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        left, right = head, head\n",
    "        remain = 1\n",
    "        remove = 0\n",
    "        while left and right:\n",
    "            if remain < m:\n",
    "                left = left.next\n",
    "                right = right.next\n",
    "                remain += 1\n",
    "            else:\n",
    "                remain = 0\n",
    "                while remove <= n and right:\n",
    "                    right = right.next\n",
    "                    remove += 1\n",
    "                left.next = right\n",
    "                remove = 1\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        if head is None:\n",
    "            return head\n",
    "\n",
    "        cur = head\n",
    "        while cur is not None:\n",
    "            m_count = 1\n",
    "            while cur is not None and m_count < m:\n",
    "                cur = cur.next\n",
    "                m_count += 1\n",
    "            \n",
    "            cur_head = cur\n",
    "            if cur_head is None:\n",
    "                break\n",
    "            \n",
    "            n_count = 0\n",
    "            while cur is not None and n_count < n:\n",
    "                cur = cur.next\n",
    "                n_count += 1\n",
    "            \n",
    "            cur_head.next = cur.next if cur is not None else None\n",
    "            cur = cur_head.next\n",
    "            \n",
    "\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        if head is None or head.next is None:\n",
    "            return head\n",
    "        current = head\n",
    "        previous = head\n",
    "        save_count = 0\n",
    "        remove_count = 0\n",
    "        while current is not None:\n",
    "            if save_count < m:\n",
    "                save_count += 1\n",
    "                previous = current\n",
    "                current = current.next\n",
    "            elif remove_count < n:\n",
    "                remove_count += 1\n",
    "                current = current.next\n",
    "            elif remove_count == n:\n",
    "                previous.next = current\n",
    "                save_count = 0\n",
    "                remove_count = 0\n",
    "        if save_count == m and remove_count == n:\n",
    "            previous.next = current\n",
    "        if remove_count > 0 and remove_count < n:\n",
    "            previous.next = current\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        dummy = ListNode(-1)\n",
    "        p = dummy\n",
    "        q = head\n",
    "        while q:\n",
    "            for _ in range(m):\n",
    "                if q:\n",
    "                    p.next = q\n",
    "                    p = p.next\n",
    "                    q = q.next\n",
    "                else:\n",
    "                    return dummy.next\n",
    "            p.next = None\n",
    "            for _ in range(n):\n",
    "                if q:\n",
    "                    q = q.next\n",
    "                else:\n",
    "                    return dummy.next\n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        fast = slow = head\n",
    "        while True:\n",
    "            for _ in range(m-1):\n",
    "                if slow.next:\n",
    "                    slow = slow.next\n",
    "                else:\n",
    "                    return head\n",
    "            \n",
    "            for _ in range(m+n):\n",
    "                if fast.next:\n",
    "                    fast = fast.next\n",
    "                else:\n",
    "                    slow.next = None\n",
    "                    return head\n",
    "\n",
    "            slow.next = fast\n",
    "            slow = fast\n",
    "            \n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        p = ListNode(0)\n",
    "        p.next = head\n",
    "        while p.next:\n",
    "            r = m\n",
    "            while p.next and r:\n",
    "                print(p.val, r)\n",
    "                p = p.next\n",
    "                r -= 1\n",
    "            q = p.next\n",
    "            t = n\n",
    "            while q and t:\n",
    "                q = q.next\n",
    "                t -= 1\n",
    "            p.next = q\n",
    "        return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        current = head\n",
    "        lis = []\n",
    "        while current:\n",
    "            for i in range(m + n):\n",
    "                try:\n",
    "                    if i > -1 and i < m:\n",
    "                        lis.append(current.val)\n",
    "                        current = current.next\n",
    "                        continue\n",
    "                except:\n",
    "                    break\n",
    "                try:\n",
    "                    if i >= m and i < n + m:\n",
    "                        current = current.next\n",
    "                except:\n",
    "                    break\n",
    "        new_head = ListNode(0)  # 新链表的头节点\n",
    "        node = new_head\n",
    "        for val in lis:\n",
    "            node.next = ListNode(val)\n",
    "            node = node.next\n",
    "        return new_head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        current = head\n",
    "        lis = []\n",
    "        while current:\n",
    "            for i in range(m + n):\n",
    "                try:\n",
    "                    if i > -1 and i < m:\n",
    "                        lis.append(current.val)\n",
    "                        current = current.next\n",
    "                        continue\n",
    "                except:\n",
    "                    break\n",
    "                try:\n",
    "                    if i >= m and i < n + m:\n",
    "                        current = current.next\n",
    "                except:\n",
    "                    break\n",
    "        new_head = ListNode(0)  # 新链表的头节点\n",
    "        node = new_head\n",
    "        for val in lis:\n",
    "            node.next = ListNode(val)\n",
    "            node = node.next\n",
    "        return new_head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        current = head\n",
    "        lis = []\n",
    "        while current:\n",
    "            for i in range(m + n):\n",
    "                try:\n",
    "                    if i > -1 and i < m:\n",
    "                        lis.append(current.val)\n",
    "                        current = current.next\n",
    "                        continue\n",
    "                except:break\n",
    "                \n",
    "                try:\n",
    "                    if i >= m and i < n + m:\n",
    "                        current = current.next\n",
    "                except:\n",
    "                    break\n",
    "        new_head = ListNode(0)  # 新链表的头节点\n",
    "        node = new_head\n",
    "        for val in lis:\n",
    "            node.next = ListNode(val)\n",
    "            node = node.next\n",
    "        return new_head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def successor(self, root):\n",
    "        root = root.right\n",
    "        while root.left:\n",
    "            root = root.left\n",
    "        return root.val\n",
    "    \n",
    "    def predecessor(self, root):\n",
    "        root = root.left\n",
    "        while root.right:\n",
    "            root = root.right\n",
    "        return root.val\n",
    "\n",
    "    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        \n",
    "        if key>root.val:\n",
    "            root.right = self.deleteNode(root.right, key)\n",
    "        elif key < root.val:\n",
    "            root.left = self.deleteNode(root.left, key)\n",
    "        else:\n",
    "            # the node is a leaf\n",
    "            if not (root.left or root.right):\n",
    "                root = None\n",
    "            # the node is not a leaf and has a right child\n",
    "            elif root.right:\n",
    "                root.val = self.successor(root)\n",
    "                root.right = self.deleteNode(root.right, root.val)\n",
    "            # the node is not a leaf, has no right child, and has a left child    \n",
    "            else:\n",
    "                root.val = self.predecessor(root)\n",
    "                root.left = self.deleteNode(root.left, root.val)\n",
    "                        \n",
    "        return root\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, root, key):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type key: int\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        def helper(node, target):\n",
    "            if node.right and node.left:\n",
    "                if not node.left.right:\n",
    "                    node.val, node.left = node.left.val, node.left.left\n",
    "                else:\n",
    "                    pre, suc = node.left, node.left.right\n",
    "                    while suc.right:\n",
    "                        pre, suc = pre.right, suc.right\n",
    "                    node.val, pre.right = suc.val, suc.left\n",
    "                return node\n",
    "            if node.right:\n",
    "                return node.right\n",
    "            return node.left\n",
    "    \n",
    "        if not root:\n",
    "            return root\n",
    "        if root.val == key:\n",
    "            return helper(root, key)\n",
    "        if root.val > key:\n",
    "            root.left = self.deleteNode(root.left, key)\n",
    "        else:\n",
    "            root.right = self.deleteNode(root.right, key)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, root, key):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type key: int\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if root == None:\n",
    "            return None\n",
    "        def min_node(root):\n",
    "            if root.left == None:\n",
    "                return root\n",
    "            else:\n",
    "                return min_node(root.left)\n",
    "        def delete_min(root):\n",
    "            if root.left == None:\n",
    "                return root.right\n",
    "            else:\n",
    "                root.left = delete_min(root.left)\n",
    "                return root\n",
    "        \n",
    "        if root.val == key:\n",
    "            # if root.left == None and root.right == None:\n",
    "            #     return None\n",
    "            if root.left == None:\n",
    "                return root.right\n",
    "            elif root.right == None:\n",
    "                return root.left\n",
    "            else:\n",
    "                successor  = min_node(root.right)\n",
    "                print(successor.left,successor.right)\n",
    "                successor.left,successor.right = root.left,delete_min(root.right)\n",
    "                return successor\n",
    "            return root\n",
    "        elif key < root.val:\n",
    "            root.left = self.deleteNode(root.left,key)\n",
    "        else:\n",
    "            root.right = self.deleteNode(root.right,key)\n",
    "        \n",
    "        \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def successor(self, root):\n",
    "        \"\"\"\n",
    "        One step right and then always left\n",
    "        \"\"\"\n",
    "        root = root.right\n",
    "        while root.left:\n",
    "            root = root.left\n",
    "        return root.val\n",
    "    \n",
    "    def predecessor(self, root):\n",
    "        \"\"\"\n",
    "        One step left and then always right\n",
    "        \"\"\"\n",
    "        root = root.left\n",
    "        while root.right:\n",
    "            root = root.right\n",
    "        return root.val\n",
    "        \n",
    "    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:\n",
    "        if not root:\n",
    "            return None\n",
    "        \n",
    "        # delete from the right subtree\n",
    "        if key > root.val:\n",
    "            root.right = self.deleteNode(root.right, key)\n",
    "        # delete from the left subtree\n",
    "        elif key < root.val:\n",
    "            root.left = self.deleteNode(root.left, key)\n",
    "        # delete the current node\n",
    "        else:\n",
    "            # the node is a leaf\n",
    "            if not (root.left or root.right):\n",
    "                root = None\n",
    "            # the node is not a leaf and has a right child\n",
    "            elif root.right:\n",
    "                root.val = self.successor(root)\n",
    "                root.right = self.deleteNode(root.right, root.val)\n",
    "            # the node is not a leaf, has no right child, and has a left child    \n",
    "            else:\n",
    "                root.val = self.predecessor(root)\n",
    "                root.left = self.deleteNode(root.left, root.val)\n",
    "                        \n",
    "        return root\n",
    "\n",
    "\n",
    "                    \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# 失敗\n",
    "# class Solution:\n",
    "#     def deleteNode(self, root: TreeNode, key: int) -> TreeNode:\n",
    "        \n",
    "#         def dfs(node):\n",
    "\n",
    "#             if node.val > key:\n",
    "#                 dfs(node.left)\n",
    "#             elif node.val < key:\n",
    "#                 dfs(node.right)\n",
    "#             else:\n",
    "#                 if (node.left == None) and (node.right == None):\n",
    "#                     node = None\n",
    "#                 elif (node.left != None) and (node.left == None):\n",
    "#                     node = node.left\n",
    "#                 elif (node.left == None) and (node.left != None):\n",
    "#                     node = node.right\n",
    "#                 else:\n",
    "#                     return\n",
    "#                     temp = node.right\n",
    "#                     node = node.left\n",
    "#                     key2 = temp.val\n",
    "#                     while True:\n",
    "#                         if node == None:\n",
    "#                             node = temp\n",
    "#                         if node.val > key2:\n",
    "#                             node = node.left\n",
    "#                         elif node.val < key2:\n",
    "#                             node = node.left\n",
    "\n",
    "#         dfs(root)\n",
    "#         return root\n",
    "\n",
    "class Solution(object):\n",
    "    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:\n",
    "        \n",
    "        if not root: return None;\n",
    "        if root.val > key:\n",
    "            root.left = self.deleteNode(root.left, key)\n",
    "        elif root.val < key:\n",
    "            root.right = self.deleteNode(root.right, key)\n",
    "        else:\n",
    "            if not root.left or not root.right:\n",
    "                root = root.left if root.left else root.right\n",
    "            else:\n",
    "                cur = root.right\n",
    "                while cur.left: cur = cur.left\n",
    "                root.val = cur.val\n",
    "                root.right = self.deleteNode(root.right, cur.val)\n",
    "            \n",
    "        return root;\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:\n",
    "        if not root: return\n",
    "        if root.val > key: \n",
    "            root.left = self.deleteNode(root.left, key)\n",
    "        elif root.val < key: \n",
    "            root.right = self.deleteNode(root.right, key)\n",
    "        else:\n",
    "            if not root.left or not root.right:\n",
    "                root = root.left if root.left else root.right\n",
    "            else:\n",
    "                cur = root.right\n",
    "                while cur.left: cur = cur.left\n",
    "                root.val = cur.val\n",
    "                root.right = self.deleteNode(root.right, cur.val)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "class TreeNode:\r\n",
    "    def __init__(self, x):\r\n",
    "        self.val = x\r\n",
    "        self.left = None\r\n",
    "        self.right = None\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def deleteNode(self, root, key):\r\n",
    "        if not root:\r\n",
    "            return None\r\n",
    "        if root.val == key:\r\n",
    "            # 第一种情况：被删除的节点是叶子节点\r\n",
    "            if not root.left and not root.right:\r\n",
    "                return None\r\n",
    "            # 第二种情况，只有一个非空子节点\r\n",
    "            if not root.left:\r\n",
    "                return root.right\r\n",
    "            if not root.right:\r\n",
    "                return root.left\r\n",
    "            # 第三种情况：含有左右子树。可以让右子树中最小的那个节点来接替自己\r\n",
    "            if root.left and root.right:\r\n",
    "                minNode = self.getMin(root.right)\r\n",
    "                root.val = minNode.val\r\n",
    "                root.right = self.deleteNode(root.right, minNode.val)\r\n",
    "\r\n",
    "        if root.val > key:\r\n",
    "            root.left = self.deleteNode(root.left, key)\r\n",
    "        if root.val < key:\r\n",
    "            root.right = self.deleteNode(root.right, key)\r\n",
    "        return root\r\n",
    "    \r\n",
    "    def getMin(self, node):\r\n",
    "        while node.left:\r\n",
    "            node = node.left\r\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:\n",
    "        if root is None: # case 0 要删除的节点不存在\n",
    "            return root\n",
    "        if root.val > key: # 要删除的结点在左子树\n",
    "            root.left = self.deleteNode(root.left, key)\n",
    "        elif root.val < key: # 要删除的结点在右子树\n",
    "            root.right = self.deleteNode(root.right, key)\n",
    "        else: # 已经找到了要删除的结点,开始进行删除操作\n",
    "            # case1 没有孩子,直接删除返回空\n",
    "            if root.left is None and root.right is None:\n",
    "                root = None\n",
    "                return root\n",
    "            # case2 只有一个孩子,左孩子,让左孩子即位\n",
    "            elif root.left is not None and root.right is None:\n",
    "                tmp = root.left\n",
    "                root = None\n",
    "                return tmp\n",
    "            # case3 只有一个孩子,右孩子,让右孩子即位\n",
    "            elif root.right is not None and root.left is None:\n",
    "                tmp = root.right\n",
    "                root = None\n",
    "                return tmp\n",
    "            # case4 有两个孩子,和右子树 left most交换后在右子树中删除 left most\n",
    "            else:\n",
    "                curr = root.right # 右子树\n",
    "                while curr.left: # find left most\n",
    "                    curr = curr.left\n",
    "                # 退出while循环时候的curr就是left most\n",
    "                root.val = curr.val # 即位\n",
    "                root.right = self.deleteNode(root.right, curr.val) # 在右子树中删除该结点后作为新的右子树\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def find_pre_node(self, head):\n",
    "        #中序遍历head的前一个节点，即比当前节点小（左子树）的最大节点\n",
    "        while head.right:\n",
    "            head = head.right\n",
    "        return head\n",
    "    \n",
    "    def find_after_node(self, head):\n",
    "        #中序遍历head的后一个节点，即比当前节点大（右子树）的最小节点\n",
    "        while head.left:\n",
    "            head = head.left\n",
    "        return head\n",
    "        \n",
    "\n",
    "    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:\n",
    "        if not root:\n",
    "            return None\n",
    "\n",
    "        if root.val == key:\n",
    "            if root.left is None and root.right is None:\n",
    "                root = None \n",
    "            elif root.right:\n",
    "                after_node = self.find_after_node(root.right)\n",
    "                root.val = after_node.val\n",
    "                root.right = self.deleteNode(root.right, after_node.val)\n",
    "            else:\n",
    "                before_node = self.find_pre_node(root.left)\n",
    "                root.val = before_node.val\n",
    "                root.left = self.deleteNode(root.left, before_node.val)\n",
    "\n",
    "        elif root.val < key:\n",
    "            root.right = self.deleteNode(root.right, key)\n",
    "        else:\n",
    "            root.left = self.deleteNode(root.left, key)\n",
    "\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:\n",
    "        if root is None:\n",
    "            return None\n",
    "        if root.val > key:\n",
    "            root.left = self.deleteNode(root.left, key)\n",
    "            return root\n",
    "        if root.val < key:\n",
    "            root.right = self.deleteNode(root.right, key)\n",
    "            return root\n",
    "        # 找到了位置\n",
    "        if root.left is None and root.right is None:\n",
    "            return None\n",
    "        if root.left is None:\n",
    "            return root.right\n",
    "        if root.right is None:\n",
    "            return root.left\n",
    "        # 有两个儿子，找到右侧子树最小节点\n",
    "        tmpNode = root.right\n",
    "        while tmpNode.left is not None:\n",
    "            tmpNode = tmpNode.left\n",
    "        root.val = tmpNode.val\n",
    "        root.right = self.deleteNode(root.right, root.val)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:\n",
    "        print('..............?')\n",
    "        print(root)\n",
    "        print(key)\n",
    "        \"\"\"\n",
    "        删除其实是查 + 改\n",
    "        改的话，会返回一个修改之后的根节点。需要被接收\n",
    "\n",
    "        \"\"\"\n",
    "        if root is None:\n",
    "            return None\n",
    "        \n",
    "        if key == root.val:\n",
    "            print('im here')\n",
    "            if root.left is None and root.right is None: return None\n",
    "            if root.left and root.right is None: return root.left\n",
    "            if root.right and root.left is None: return root.right\n",
    "\n",
    "            # both child are there\n",
    "            right_min = self._find_right_min(root.right)\n",
    "            print(right_min)\n",
    "            # replace node\n",
    "            root.val = right_min.val\n",
    "            root.right = self.deleteNode(root.right, right_min.val)\n",
    "        \n",
    "        if key < root.val:\n",
    "            root.left = self.deleteNode(root.left, key)\n",
    "        \n",
    "        if key > root.val:\n",
    "            root.right = self.deleteNode(root.right, key)\n",
    "        return root\n",
    "    \n",
    "    def _find_right_min(self, node: TreeNode) -> TreeNode:\n",
    "        if node is None:\n",
    "            return\n",
    "        while node and node.left:\n",
    "            node = node.left\n",
    "        \n",
    "        return node\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:\n",
    "        print(root)\n",
    "        def delete(root, key, left):\n",
    "            if not root:\n",
    "                return left\n",
    "            if root.val == key:\n",
    "                return delete(root.right, key, root.left)\n",
    "            elif root.val < key:\n",
    "                root.right = delete(root.right, key, left)\n",
    "                return root\n",
    "            else:\n",
    "                root.left = delete(root.left, key, left)\n",
    "                return root\n",
    "        \n",
    "        return delete(root, key, None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def successor(self, root):\n",
    "        root = root.right\n",
    "        while root.left:\n",
    "            root = root.left\n",
    "        return root.val\n",
    "    def precessor(self, root):\n",
    "        root = root.left\n",
    "        while root.right:\n",
    "            root = root.right\n",
    "        return root.val\n",
    "    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:\n",
    "        if not root:\n",
    "            return None\n",
    "        if key > root.val:\n",
    "            root.right = self.deleteNode(root.right, key)\n",
    "        elif key < root.val:\n",
    "            root.left = self.deleteNode(root.left, key)\n",
    "        else:\n",
    "            if not root.left and not root.right:\n",
    "                root = None\n",
    "            elif root.right:\n",
    "                root.val = self.successor(root)\n",
    "                root.right = self.deleteNode(root.right, root.val)\n",
    "            else:\n",
    "                root.val = self.precessor(root)\n",
    "                root.left = self.deleteNode(root.left, root.val)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:\n",
    "        def deleteRoot(root):\n",
    "            if root.left is None and root.right is None:\n",
    "                root = None\n",
    "            elif root.left is not None and root.right is None:\n",
    "                root = root.left\n",
    "            elif root.left is None and root.right is not None:\n",
    "                root = root.right\n",
    "            elif root.left is not None and root.right is not None:\n",
    "                minRoot = root.left\n",
    "                # 若有右节点，说明有更小的点。\n",
    "                # 找到最小点的父节点，使其继承root的左右子树，删掉父节点的右子（即删掉最小点），然后返回\n",
    "                while minRoot.right:\n",
    "                    minRoot = minRoot.right\n",
    "                minV = minRoot.val\n",
    "                # 组装新的节点\n",
    "                minRoot.left = self.deleteNode(root.left, minV)\n",
    "                minRoot.right = root.right\n",
    "                return minRoot\n",
    "            return root\n",
    "\n",
    "        if not root:\n",
    "            return root\n",
    "        if root.val == key:\n",
    "            root = deleteRoot(root)\n",
    "        elif root.val > key:\n",
    "            root.left = self.deleteNode(root.left, key)\n",
    "        elif root.val < key:\n",
    "            root.right = self.deleteNode(root.right, key)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        dummyHead = TreeNode(left=root)\n",
    "        pre, p = dummyHead, root\n",
    "        while p and p.val != key:\n",
    "            pre = p\n",
    "            p = p.left if p.val > key else p.right\n",
    "        if not p:\n",
    "            return root\n",
    "\n",
    "        if not p.left:\n",
    "            p = p.right\n",
    "        elif not p.right:\n",
    "            p = p.left\n",
    "        else:\n",
    "            q = p.left\n",
    "            while q.right:\n",
    "                q = q.right\n",
    "            q.right = p.right.left\n",
    "            p.right.left = p.left\n",
    "            p = p.right\n",
    "            \n",
    "        if pre.left and pre.left.val == key:\n",
    "            pre.left = p\n",
    "        else:\n",
    "            pre.right = p\n",
    "\n",
    "        return dummyHead.left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        if root.val < key:\n",
    "            root.right = self.deleteNode(root.right, key)\n",
    "        elif root.val > key:\n",
    "            root.left = self.deleteNode(root.left, key)\n",
    "        else:\n",
    "            if not root.left:\n",
    "                return root.right\n",
    "            if not root.right:\n",
    "                return root.left\n",
    "            # 找到右子树的最左端点\n",
    "            cur = root.right\n",
    "            while cur.left:\n",
    "                cur = cur.left\n",
    "            # 把左子树挂到这个左端点上\n",
    "            cur.left = root.left\n",
    "            # 删除root节点\n",
    "            root = root.right\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return None\n",
    "        if root.val > key:\n",
    "            root.left = self.deleteNode(root.left, key)\n",
    "        elif root.val < key:\n",
    "            root.right = self.deleteNode(root.right, key)\n",
    "        elif root.left is None or root.right is None:\n",
    "            root = root.left if root.left else root.right\n",
    "        else:  # 当前节点值为key，且有左右子树\n",
    "            successor = root.right\n",
    "            while successor.left:  # 找到右子树中的最小值，即其左叶节点\n",
    "                successor = successor.left\n",
    "            successor.right = self.deleteNode(root.right, successor.val) # 删除这个最小值，将剩余部分作为右节点\n",
    "            successor.left = root.left \n",
    "            return successor\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:\n",
    "        def findplace(root, key):\n",
    "            if not root:\n",
    "                return root\n",
    "            ans = findplace(root.left, key)\n",
    "            if not ans:\n",
    "                if root.val == key:\n",
    "                    return root\n",
    "                ans = findplace(root.right, key)\n",
    "            if ans and not record:\n",
    "                record.append(root)\n",
    "            return ans\n",
    "        record = list()\n",
    "        node = findplace(root, key)\n",
    "        if not node:\n",
    "            return root\n",
    "        if not node.left and not node.right:\n",
    "            if node == root:\n",
    "                return None\n",
    "            elif node == record[0].left:\n",
    "                record[0].left = None\n",
    "                return root\n",
    "            else:\n",
    "                record[0].right = None\n",
    "                return root\n",
    "        if not node.left and node.right:\n",
    "            if node == root:\n",
    "                return node.right\n",
    "            elif node == record[0].left:\n",
    "                record[0].left = node.right\n",
    "                return root\n",
    "            else:\n",
    "                record[0].right = node.right\n",
    "                return root\n",
    "        if node.left and not node.right:\n",
    "            if node == root:\n",
    "                return node.left\n",
    "            elif node == record[0].left:\n",
    "                record[0].left = node.left\n",
    "                return root\n",
    "            else:\n",
    "                record[0].right = node.left\n",
    "                return root\n",
    "        if node.left and node.right:\n",
    "            if node == root:\n",
    "                node1 = node.left\n",
    "                node2 = node.right\n",
    "                ans = node2\n",
    "                while node2.left:\n",
    "                    node2 = node2.left\n",
    "                node2.left = node1\n",
    "                return ans\n",
    "            elif node == record[0].left:\n",
    "                record[0].left = node.right\n",
    "                node1 = node.left\n",
    "                node2 = node.right\n",
    "                while node2.left:\n",
    "                    node2 = node2.left\n",
    "                node2.left = node1\n",
    "                return root\n",
    "            else:\n",
    "                record[0].right = node.right\n",
    "                node1 = node.left\n",
    "                node2 = node.right\n",
    "                while node2.left:\n",
    "                    node2 = node2.left\n",
    "                node2.left = node1\n",
    "                return root\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:\n",
    "        if not root: return None\n",
    "        if root.val > key:\n",
    "            root.left = self.deleteNode(root.left, key)\n",
    "        elif root.val < key:\n",
    "            root.right = self.deleteNode(root.right, key)\n",
    "        else:\n",
    "            if not root.left: return root.right\n",
    "            if not root.right: return root.left\n",
    "            node = root.right\n",
    "            while node.left:\n",
    "                node = node.left\n",
    "            node.left = root.left\n",
    "            print(node)\n",
    "            root = root.right\n",
    "        \n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:\n",
    "        '''\n",
    "        # 递归法 版本一：\n",
    "        # 1.确定递归函数参数以及返回值：函数参数：root， key。返回值：root（根节点）\n",
    "        # 2.确定终止条件：遇到空返回，其实这也说明没找到删除的节点，遍历到空节点直接返回了\n",
    "        # 3.确定单层递归逻辑：第一种情况：没找到删除的节点，遍历到空节点直接返回了找到删除的节点；第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点；第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点；第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点；第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。\n",
    "        if not root:\n",
    "            return root\n",
    "        if root.val == key:\n",
    "            if not root.left and not root.right:\n",
    "                return None\n",
    "            elif not root.left:\n",
    "                return root.right\n",
    "            elif not root.right:\n",
    "                return root.left\n",
    "            else:\n",
    "                cur = root.right\n",
    "                while cur.left:\n",
    "                    cur = cur.left\n",
    "                cur.left = root.left \n",
    "                return root.right\n",
    "\n",
    "        if root.val > key:\n",
    "            root.left = self.deleteNode(root.left, key)\n",
    "        if root.val < key:\n",
    "            root.right = self.deleteNode(root.right, key)\n",
    "\n",
    "        return root\n",
    "        '''\n",
    "        '''\n",
    "        # 递归法 版本二：\n",
    "        if not root:\n",
    "            return root\n",
    "        if root.val == key:\n",
    "            if not root.right:\n",
    "                return root.left\n",
    "            cur = root.right\n",
    "            while cur.left:\n",
    "                cur = cur.left\n",
    "            root.val, cur.val = cur.val, root.val\n",
    "\n",
    "        root.left = self.deleteNode(root.left, key)\n",
    "        root.right = self.deleteNode(root.right, key)\n",
    "\n",
    "        return root\n",
    "        '''\n",
    "        # 迭代法\n",
    "        if not root:\n",
    "            return root\n",
    "\n",
    "        cur = root\n",
    "        pre = None\n",
    "        while cur:\n",
    "            if cur.val == key:\n",
    "                break\n",
    "            pre = cur\n",
    "            if cur.val > key:\n",
    "                cur = cur.left\n",
    "            else:\n",
    "                cur = cur.right\n",
    "\n",
    "        if not pre:\n",
    "            return self.deleteOneNode(cur)\n",
    "\n",
    "        if pre.left and pre.left.val == key:\n",
    "            pre.left = self.deleteOneNode(cur)\n",
    "        if pre.right and pre.right.val == key:\n",
    "            pre.right = self.deleteOneNode(cur)\n",
    "\n",
    "        return root\n",
    "\n",
    "    def deleteOneNode(self, cur: TreeNode) -> TreeNode:\n",
    "        if not cur:\n",
    "            return cur\n",
    "\n",
    "        if not cur.right:\n",
    "            return cur.left\n",
    "\n",
    "        cur1 = cur.right\n",
    "        while cur1.left:\n",
    "            cur1 = cur1.left\n",
    "        cur1.left = cur.left\n",
    "        return cur.right \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getSuccess(self, node):\n",
    "        node = node.right\n",
    "        while node.left:\n",
    "            node = node.left\n",
    "        return node\n",
    "\n",
    "\n",
    "    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:\n",
    "\n",
    "        if not root: return root\n",
    "\n",
    "        if key < root.val:\n",
    "            root.left = self.deleteNode(root.left, key)\n",
    "        elif key > root.val:\n",
    "            root.right = self.deleteNode(root.right, key)\n",
    "        else:\n",
    "            if not root.left and not root.right:\n",
    "                root = None\n",
    "            elif root.left and not root.right:\n",
    "                root = root.left\n",
    "            elif root.right and not root.left:\n",
    "                root = root.right\n",
    "            else:\n",
    "                node = self.getSuccess(root)\n",
    "                root.val = node.val\n",
    "                root.right = self.deleteNode(root.right, node.val)\n",
    "        \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val=node.next.val\n",
    "        node.next=node.next.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        if node.next.next == None:\n",
    "            node.val = node.next.val\n",
    "            node.next = None\n",
    "            \n",
    "        else:\n",
    "            node.val = node.next.val\n",
    "            node.next = node.next.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        next_node = node.next\n",
    "        node.val = next_node.val\n",
    "        node.next = next_node.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "       \n",
    "        node.val=node.next.val\n",
    "        node.next=node.next.next\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val=node.next.val\n",
    "        node.next=node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val=node.next.val\n",
    "        node.next=node.next.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val, node.next = node.next.val, node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        if node.next.next==None:\n",
    "            node.val=node.next.val\n",
    "            node.next=None\n",
    "        else:\n",
    "            node.val=node.next.val\n",
    "            # node.next=node.next.next\n",
    "            self.deleteNode(node.next)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        if node.next.next==None:\n",
    "            node.val=node.next.val\n",
    "            node.next=None\n",
    "        else:\n",
    "            node.val=node.next.val\n",
    "            # node.next=node.next.next\n",
    "            self.deleteNode(node.next)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next= node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        while node.next.next is not None:\n",
    "            node.val = node.next.val\n",
    "            node = node.next\n",
    "        \n",
    "        node.val = node.next.val\n",
    "        del node.next\n",
    "        node.next = None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        if node.next.next == None:\n",
    "            node.val = node.next.val\n",
    "            node.next = None\n",
    "            return\n",
    "        node.val = node.next.val\n",
    "        return self.deleteNode(node.next)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val;\n",
    "        node.next = node.next.next;\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def deleteNode(self, node):\n",
    "        \"\"\"\n",
    "        :type node: ListNode\n",
    "        :rtype: void Do not return anything, modify node in-place instead.\n",
    "        \"\"\"\n",
    "        node.val = node.next.val\n",
    "        node.next = node.next.next"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
